コンテンツにスキップ

ウルフラム・コード

出典: フリー百科事典『ウィキペディア(Wikipedia)』

ウルフラム・コード (: Wolfram code) は、広く使用されている[1]1次元のセル・オートマトン規則の番号付けルールである。この番号付けは、1983年のスティーブン・ウルフラムの論文[2]で導入され、著書A New Kind of Science[3]で一般化された。

定義[編集]

ウルフラム・コードは、オートマトンの各セルの新しい状態をその近傍の状態の関数として指定するテーブルが、S-進数[訳語疑問点]k-桁の数字として解釈できるという観察に基づいている。ここで、

  • S はオートマトンの各セルが持つことのできる状態の数、
  • k = S2n + 1 は近傍の状態の総数 [注釈 1]
  • nは近傍の半径

とする。従って、特定のルールのウルフラム・コードは、0 から SS2n + 1 − 1 の範囲[注釈 2]であり、S-aryから10進数表記に変換される。その計算は以下の通りである。

  1. セルの近傍 2n + 1 セル分の状態は、全部で S2n + 1 通りある。これをすべてリストする。
  2. 各状態 S 進数との数値として解釈し、数値の降順に並べ替える。
  3. 各状態について、繊維ルールに基づいて、次のイテレーションにおけるセルの状態を計算し、リストする。
  4. 得られた状態のリストを再び S 進数の数値として解釈し、この数を10進数に変換する。この結果の10進数がウルフラム・コードである。

ウルフラム・コードは、近傍のサイズ・形状も、状態の数も指定していない。これらは、文脈から既知であると仮定されている。そのような文脈なしに使われて場合は、コードは初等セル・オートマトン英語版を指すものと想定されることが多い。すなわち、2状態1次元3近傍セル・オートマトンである。ウルフラムは彼の著書で広範囲に調査している。このクラスの注目すべきルール番号には、ルール30ルール110英語版ルール184がある。ルール90英語版も2を法とするパスカルの三角形を形成するため興味深い。「ルール37R」のように末尾に「R」が付いたこのタイプのコードは、同じ近傍構造を持つ二次セル・オートマトン英語版を示す。

厳密には、有効範囲内のすべてのウルフラム・コードは異なる規則を定義しているが、これらの規則のいくつかは同型であり、通常は同値なものと見做される。たとえば、上記のルール110は、124、137、193と同型であり、これらは元のルールから、左右反転と、状態の再番号付けによって取得できる。慣例では、そのような各同型クラスは、コード番号が最も小さいルールによって表される。ウルフラム表記、特に10進表記の欠点は、同型が他の表記法に比べて分かりにくくなることである。それにもかかわらず、ウルフラム・コードは、1次元セル・オートマトンを参照するデファクトスタンダードになっている。

[編集]

ここでは1次元2状態3近傍セルオートマトンの例を示す。

計算手順のステップ1 現在の状態 111 110 101 100 011 010 001 000
ステップ2 二進数として解釈 (ソート順) 7 6 5 4 3 2 1 0
ステップ3 中央のセルの次の状態 0 0 0 1 1 1 1 0

この表を二段目の「二進数として解釈 (ソート順)」に記載の数字が降順になるように各列を並び替える(この表ではすでに降順に並んでいるので、そのままでよい)。並び替えた後の表で、三段目の「中央のセルの次の状態」のデータを並べた0、0、0、1、1、1、1、0を2進数 と解釈し、10進数に変換すると、30である。従って、この規則はルール30と呼ばれる。

一般化セル・オートマトン[編集]

一般化して、D-次元空間で、近傍サイズが nであり、各セルの状態数が S であるようなセル・オートマトンを考える。この時、可能なルールの総数は、

R=SS(2n+1)D

で与えられる。

もっとも一般的な例は S = 2、n = 1、D = 1の場合で、ルールの総数は R = 256 となる。可能なルールの総数は、系の次元に大きく依存する。例えば、空間の次元 (D) を1から2に増加すると、ルールの総数は、256から2512に増加する (これはおよそ1.341×10154である) 。

脚注[編集]

注釈[編集]

  1. ^ 近傍は自身を含めて 2n + 1 セル分。各セルは S 通りの状態があるので、近傍の状態の総数は S 種類の中から2n + 1 個選ぶ重複順列の総数になる
  2. ^ セル・オートマトンの遷移規則は、 2n + 1 セル分の状態を入力とし、1セル分の状態を返す関数である。この関数は、k 通りの入力に対して、S 個の状態のいずれかを対応させるものである。このような関数は、S 種類の中から(重複を許して) k 回選ぶ重複順列と対応しているので、Sk 通りのパターンがあり得る。

参考文献[編集]

  1. ^ Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010). Cellular Automata and Groups. Springer. p. 28. doi:10.1007/978-3-642-14034-1. ISBN 978-3-642-14034-1. https://link.springer.com/book/10.1007/978-3-642-14034-1 2022年10月22日閲覧。 
  2. ^ Wolfram, Stephen (July 1983). “Statistical Mechanics of Cellular Automata”. Reviews of Modern Physics 55 (3): 601–644. Bibcode1983RvMP...55..601W. doi:10.1103/RevModPhys.55.601. 
  3. ^ Wolfram, Stephen (May 14, 2002). A New Kind of Science. Wolfram Media, Inc.. ISBN 1-57955-008-8. http://www.wolframscience.com/nksonline